// https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 字典树(Trie)高效存储和检索字符串集合
// 2. 每个节点包含26个子节点指针，对应小写字母
// 3. 插入时按字符路径创建节点，单词结尾标记isEnd
// 4. 搜索时遍历字符路径，检查节点存在性和结束标记
// 5. 前缀查找只需验证路径存在性
// 6. 时间复杂度：O(L)，空间复杂度：O(N×L)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

struct TrieNode
{
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie 
{
private:
    TrieNode* root;
public:
    Trie() 
    {
        root = new TrieNode();
    }

    ~Trie()
    {
        destroyTrie(root);
    }
    
    void insert(string word) 
    {
        TrieNode* cur = root;

        for (const char& ch : word)
        {
            int index = ch - 'a';
            if (cur->children[index] == nullptr)
            {
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
        }

        cur->isEnd = true;
    }
    
    bool search(string word) 
    {
        TrieNode* cur = findNode(word);
        return cur != nullptr && cur->isEnd == true;
    }
    
    bool startsWith(string prefix) 
    {
        return findNode(prefix) != nullptr;
    }
private:
    Trie(const Trie&) = delete;
    Trie& operator=(const Trie&) = delete;

    TrieNode* findNode(const string& word)
    {
        TrieNode* cur = root;

        for (const char& ch : word)
        {
            int index = ch - 'a';
            if (cur->children[index] == nullptr)
            {
                return nullptr;
            }
            cur = cur->children[index];
        }

        return cur;
    }

    void destroyTrie(TrieNode* root)
    {
        if (root == nullptr)
        {
            return ;
        }

        for (int i = 0 ; i < 26 ; i++)
        {
            destroyTrie(root->children[i]);
        }

        delete root;
    }
};

int main()
{
    Trie trie;
    trie.insert("apple");
    trie.insert("app");

    cout << trie.search("apple") << endl;    
    cout << trie.search("app") << endl;       
    cout << trie.search("ap") << endl;       
    cout << trie.startsWith("ap") << endl;  

    return 0;
}